//
// Created by shenbin on 2022/4/25.
// https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/
//

#ifndef ALGORITHM_TRAINNING_W02_H03_LC1074_H
#define ALGORITHM_TRAINNING_W02_H03_LC1074_H

#include <unordered_map>
#include <vector>

using namespace std;

/**
 *
 */
class LeetCode1074 {
public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int rowCount = matrix.size();
        int colCount = matrix[0].size();
        int ans = 0, sum = 0;
        // 按列累计
        for (int i = 0; i < rowCount; i++)
            for (int j = 1; j < colCount; j++)
                matrix[i][j] += matrix[i][j - 1];
        for (int k = 0; k < colCount; k++) {
            for (int j = k; j < colCount; j++) {
                int sum = 0;
                unordered_map<int, int> mp = {{0, 1}};
                for (int i = 0; i < rowCount; i++) {
                    sum += (k == 0 ? matrix[i][j] : matrix[i][j] - matrix[i][k - 1]);
                    if (mp.count(sum - target))
                        ans += mp[sum - target];
                    mp[sum]++;
                }
            }
        }
        return ans;
    }

private:

};

#endif //ALGORITHM_TRAINNING_W02_H03_LC1074_H
